UVa/843 - Crypt kicker/843.3.cpp

   1 #include <sstream>
   2 #include <iostream>
   3 #include <map>
   4 #include <string>
   5 #include <vector>
   6 #include <set>
   7
   8 using namespace std;
   9
  10 map<int, set<string> > dict;
  11 map<char, char> solucion;
  12
  13
  14 bool contradice(const string &origen, const string &destino,  map<char, char> crypt){
  15   if (origen.length() != destino.length()) return true;
  16
  17   for (int i=0; i<origen.size(); ++i){
  18     if (crypt.count(origen[i]) == 1){
  19       if (crypt[origen[i]] != destino[i]){
  20         return true;
  21       }
  22     }else{
  23       for (map<char, char>::iterator j = crypt.begin(); j != crypt.end(); ++j){
  24         if ((*j).second == destino[i]) return true;
  25       }
  26       crypt[origen[i]] = destino[i];
  27     }
  28   }
  29   return false;
  30 }
  31
  32 map<char, char> asignar(const string &origen, const string &destino, map<char, char> crypt){
  33   if (origen.size() == destino.size()){
  34     for (int i=0; i<origen.size(); ++i){
  35       crypt[origen[i]] = destino[i];
  36     }
  37   }
  38   return crypt;
  39 }
  40
  41 bool bt(const int &i, const vector<string> &words, map<char, char> crypt){
  42   if (i >= words.size()){
  43     solucion = crypt;
  44     return true;
  45   }
  46
  47   int len = words[i].length();
  48   set<string> possible = dict[len];
  49
  50   for (set<string>::iterator j = possible.begin(); j != possible.end(); ++j){
  51     if (!contradice(words[i], (*j), crypt)){
  52       if (bt(i+1, words, asignar(words[i], (*j), crypt))){
  53         return true;
  54       }
  55
  56     }
  57
  58   }
  59   return false;
  60 }
  61
  62 int main(){
  63   int n;
  64   cin >> n;
  65   while (n--){
  66     string s;
  67     cin >> s;
  68     dict[s.length()].insert(s);
  69   }
  70   getchar();
  71   string line;
  72   while (getline(cin, line)){
  73
  74     if (line == ""){
  75       cout << "\n";
  76       continue;
  77     }
  78
  79     vector<string> words;
  80     stringstream ss(line);
  81     string word;
  82     while (ss >> word){
  83       words.push_back(word);
  84     }
  85
  86     if (bt(0, words, map<char, char>() )){
  87       for (int i=0; i<line.size(); ++i){
  88         if (line[i] == ' ') cout << " ";
  89         else cout << solucion[line[i]];
  90       }
  91       cout << endl;
  92     }else{
  93       for (int i=0; i<line.size(); ++i){
  94         if (line[i] == ' ') cout << " ";
  95         else cout << "*";
  96       }
  97       cout << endl;
  98     }
  99   }
 100   return 0;
 101 }